1. Field of the Invention
The present invention relates to a network switch such as a router or switch, etc., that performs data transfer in a network (in the following description, these apparatuses are referred to by the generic term xe2x80x9cswitchxe2x80x9d), and more particularly relates to a switch that performs switch scheduling in accordance with priority levels set in the data, together with the associated scheduler and switch scheduling method.
2. Description of the Prior Art
Previously, data traffic on the Internet has been characterized as of xe2x80x9cbest effortxe2x80x9d type, and traffic Quality of Service (QoS) has not been implemented with respect to zones, delays, fluctuation s, etc. When a switch that transfers IP packets received a packet, it has only performed packet transfer with the QoS available at the time the packet was received, and QoS has not been assured.
However, the emergence of protocols such as RSVP (Reservation Protocol) and DiffServ (Differentiated Service) has made it possible for traffic QoS to be assured as a protocol, even on the Internet.
With switches, also, technology has been proposed for implementing QoS assurance with traffic classified by QoS. An example of this kind of prior art is the switch shown in Japanese Patent Laid-Open No. 10-200550.
Meanwhile, functions provided by VoIP (Voice over IP), etc., have made it possible to accommodate telephonic speech on the Internet, and there have been moves by telephone companies to implement telephone networks by means of the Internet. As a result, QoS assurance requirements for the Internet have become even more stringent in recent years.
FIG. 14 shows the configuration of a conventional switch, and FIG. 15 shows the switching operation by the switch in FIG. 14 in its flowchart. With reference now to FIG. 14, the switch comprises a plurality of input ports 110a to 110b that input data, a plurality of output ports 140a to 140b that output data, a switching execution block 130 that switches data input from the input ports 110a to 110b and transmits it to the output ports 140a to 140b, and a scheduler 120 that controls switching by the switching execution block 130. The input ports 110a to 110b each comprise queues 111 provided for each output port.
With reference now to the flowchart in FIG. 15, first, when an input port 110a to 110b receives data destined for one of the output ports 140a to 140b, that data is queued in a per-output-port queue 111 (step 1501). Next, in order to request switch 130 connection, the input port 110a to 110b sends the scheduler 120 a request for connection to the desired output port (step 1502).
When the scheduler 120 accepts connection requests from input ports 110a to 110b, it performs connection destination allocation in such a way as to avoid mutual collision between connections from individual input ports 110a to 110b to output ports 140a to 140b (step 1503). Then, it sets the switch 130 according to the allocation (step 1504), and returns Grant signals to the input ports 110a to 110b indicating the respective connection destination output ports 140a to 140b (step 1505).
The individual input port 110a to 10b transmits to the switch 130 the data destined for the connection destination output port reported by the Grant signal (step 1506). Then, the switch 130 performs switching in accordance with the setting by the scheduler 120, and transmits the accepted data to the individual output port 140a to 140b (step 1507).
However, in switch scheduling by means of the prior art described above, uniform scheduling is performed that takes no account of the quality, priority, etc., of the data being switched. Consequently, when performing transfer via the Internet of traffic, such as telephonic speech, with stringent requirements in terms of delay characteristics, or when traffic using a number of protocols with differing quality and characteristics is handled by a single switch, it is not possible to achieve switching in accordance with traffic quality.
In Japanese Patent Laid-Open No. 8-56230, a switching system is shown that implements switch scheduling according to priority. In the switching system shown in this Patent Publication, traffic of all priorities is simultaneously scheduled by a single scheduler. That is to say, as shown in FIG. 16, the scheduler 1610 has, for each cell entry, a tag register 1620 that has tags showing cell priority, and a comparator 1630 that compares the values of the priorities held in the tag register 1620, and performs scheduling by comparing the cell priorities sequentially, one by one. Therefore, the scheduler 1610 must perform the task of scheduling by judging all priorities within one cell time interval (one time slot). Moreover, a special scheduling algorithm must be provided in order to satisfy this condition.
Since, in conventional switch scheduling, uniform scheduling is performed that takes no account of the quality, priority, etc., of the data being switched, as described above, a defect of conventional switch scheduling is that it may not be possible to implement switching in accordance with traffic quality.
Moreover, a shortcoming of the switching system described in Japanese Patent Laid-Open No. 8-56230 is that the configuration of the apparatus is made complex by the need to perform the task of scheduling by judging all priorities within one cell time interval (one time slot). A further shortcoming of this switching system is that flexible setting changes cannot be made because of the need for a special scheduling algorithm.
The present invention has as an objective the provision of a switch, and its associated scheduler and switch scheduling method, that solve the above mentioned defects in the conventional system, and implement flexible switch scheduling in accordance with priority levels set in the data, by means of a simple apparatus configuration.
Further, the present invention has as an objective the provision of a switch, and its associated scheduler and switch scheduling method, that can easily be introduced into a network system by implementing switch scheduling that includes priority control using, without modification, the conventional means of switch scheduling (algorithm, etc.) that does not include priority control.
An aspect of the present invention that attains the above mentioned object comprises a plurality of input ports that input transfer data and a plurality of output ports that output transfer data; means for executing switching that switches transfer data that is input from said input ports and transmits it to said output ports; and a scheduler that controls switching by said means for executing switching in response to connection requests for said transfer data from said input ports; wherein said scheduler, in a switch that is provided in a network and performs IP packet transfer, comprises distribution means that inputs said transfer data from said input ports and distributes connection requests for said transfer data in accordance with priority levels set in said transfer data that is input; first means for switch connection allocation that performs switch connection allocation corresponding to connection requests for said transfer data with a high priority level from among the connection requests distributed by said distribution means; second means for switch connection allocation that performs switch connection allocation corresponding to connection requests for said transfer data with a low priority level from among the connection requests distributed by said distribution means; combination means that combines the results of switch connection allocation by said first means for switch connection allocation and said second means for switch connection allocation; and means for permitting switch connection that, on the basis of the result of switch connection allocation combined by said combination means, sets said means for executing switching and performs notification that permits switch connection for said input ports; wherein said second means for switch connection allocation comprises masking means for masking, prior to execution of switch connection allocation processing, said connection requests that duplicate the result of switch connection allocation by said first means for switch connection allocation.
In another aspect, the present invention further comprises third means for switch connection allocation that performs switch connection allocation corresponding to connection requests for said transfer data with a lower priority level than said transfer data corresponding to said second means for switch connection allocation; and second combination means that combines the result of switch connection allocation combined by said combination means and the result of switch connection allocation by said third means for switch connection allocation; wherein said third means for switch connection allocation comprises masking means for masking, prior to execution of switch connection allocation processing, said connection requests that duplicate the result of switch connection allocation combined by said combination means.
In still another aspect, the present invention comprises in stages said third means for switch connection allocation and said second combination means, in accordance with the number of said connection requests distributed by said distribution means.
In still another aspect, the present invention further comprises means of selection, provided between said combination means and said means for permitting switch connection, whereby the result of switch connection allocation by said first means for switch connection allocation and the result of switch connection allocation combined by said combination means are input, and one or other of said switch connection allocation results is output selectively and sent to said means for permitting switch connection; wherein said means for permitting switch connection, on the basis of the result of combined switch connection allocation output from said selection means, sets said means for executing switching and performs notification that permits switch connection for said input ports.
Moreover, another aspect of the present invention that attains the above mentioned object comprises a plurality of input ports that input transfer data and a plurality of output ports that output transfer data; means for executing switching that switches transfer data that is input from said input ports and transmits it to said output ports; and a scheduler that controls switching by said means for executing switching in response to connection requests for said transfer data from said input ports; wherein the switch scheduling method in a switch that is provided in a network and performs IP packet transfer comprises the step of inputting said transfer data from said input ports and distributing connection requests for said transfer data in accordance with priority levels set in said transfer data that is input; the step of performing switch connection allocation corresponding to connection requests for said transfer data with a high priority level from among the connection requests distributed by said distribution step; the step of performing switch connection allocation corresponding to connection requests for said transfer data with a low priority level from among the connection requests distributed by said distribution means; the step of combining the results of switch connection allocation by said two switch connection allocation steps; and the step of setting said means for executing switching and performing notification that permits switch connection for said input ports, on the basis of the result of switch connection allocation combined by said combination step; wherein said step of allocating switch connection corresponding to connection requests for said transfer data with a low priority level includes the step of masking, prior to execution of switch connection allocation processing, said connection requests that duplicate the result of switch connection allocation by said first switch connection allocation means.
In still another aspect, said step of switch connection allocation corresponding to connection requests for said transfer data with a low priority level, and said combination step, are repeated in stages, in accordance with the number of said connection requests distributed by said distribution means.
In still another aspect, the present invention further comprises the step, provided between said combination step and said permitting switch connection step, of inputting the result of switch connection allocation by the step of switch connection allocation corresponding to said connection requests for said transfer data with a high priority level, and the result of switch connection allocation combined in said combination step, and outputting selectively one or other of said switch connection allocation results; wherein said means for executing switching is set, and notification is performed that permits switch connection for said input ports, on the basis of the result of switch connection allocation selected in said selection step, in said permitting switch connection step.
In still another aspect, said step of switching connection allocation corresponding to data transfer connection requests is executed in parallel by means of pipeline processing for each priority level.